\documentclass[a4paper]{article}
\usepackage{xeCJK}
%\setlength\textwidth{180pt}
\usepackage{indentfirst}
\usepackage{pdfpages} 
\usepackage{listings}
\usepackage{color}
\usepackage[svgnames]{xcolor}
\usepackage{tikz}
%\usepackage{minted}
\usepackage{fancybox}
\usetikzlibrary{decorations.pathmorphing} % noisy shapes
\usetikzlibrary{fit}					% fitting shapes to coordinates

\usepackage[left=1.8cm,right=1.8cm,top=2cm,bottom=1.5cm]{geometry}
\setmainfont{DejaVu Sans}
\setCJKmainfont{WenQuanYi Micro Hei}
\setCJKfamilyfont{antony}{WenQuanYi Micro Hei}
%\lstset{ language=C, numbers=left, basicstyle=\small\ttfamily\bfseries,
 % keywordstyle=\color{blue}, commentstyle=\color{comment},
  %stringstyle=\color{red}, frame=shadowbox, breaklines=true,
  %backgroundcolor=\color{lightgray},escapeinside=`` }


\lstset{ %
language=C,                % choose the language of the code
basicstyle=\CJKfamily{antony},       % the size of the fonts that are used for the code
numbers=left,                   % where to put the line-numbers
numberstyle=\footnotesize,      % the size of the fonts that are used for the line-numbers
stepnumber=0,                   % the step between two line-numbers. If it is 1 each line will be numbered
numbersep=5pt,                  % how far the line-numbers are from the code
backgroundcolor=\color{white},  % choose the background color. You must add \usepackage{color}
showspaces=false,               % show spaces adding particular underscores
showstringspaces=false,         % underline spaces within strings
showtabs=false,                 % show tabs within strings adding particular underscores
frame=single,   		% adds a frame around the code
tabsize=2,  		% sets default tabsize to 2 spaces
captionpos=b,   		% sets the caption-position to bottom
breaklines=true,    	% sets automatic line breaking
breakatwhitespace=false,    % sets if automatic breaks should only happen at whitespace
escapeinside={\%}{},          % if you want to add a comment within your code
keywordstyle=\CJKfamily{antony}\color{blue},
identifierstyle=,
%numberstyle=\color[RGB]{0,192,192},
commentstyle=\it\color[RGB]{0,96,96},
backgroundcolor=\color[RGB]{245,245,244},
stringstyle=\rmfamily\slshape\color[RGB]{128,0,0}
}


\definecolor{lightgray}{RGB}{230,230,230}
\definecolor{comment}{RGB}{0,180,100}
\newcommand{\clbox}[1]{\noindent\fcolorbox{black}{Lavender}{\vbox{#1}}}
\newcommand{\qebox}[1]{\noindent\fcolorbox{black}{pink}{\vbox{#1}}}
\newcommand{\imwords}[1]{\textbf{\color{red}#1}}
\newcommand{\ccode}[1]{\setmainfont{DejaVu Sans Mono}\begin{lstlisting}#1\end{lstlisting}\setmainfont{DejaVu Sans}}
\newcommand{\sans}{\setmainfont{DejaVu Sans}}
\newcommand{\mono}{\setmainfont{DejaVu Sans Mono}}
% 非常重要, listings关闭非ASCII字符兼容
\lstset{extendedchars=false}
\title{JOS Lab5}
\author{00848161	谢睿明}
\date{}
\begin{document}
\maketitle
\par{Lab5使用微内核实现一个简单的文件系统，其余环境可以通过IPC信号的发送和接收与文件系统通信，实现创建文件、删除文件、查找文件等等功能。}
\section{Exercise 1}
\clbox{Modify your kernel's environment initialization function, env\_alloc in env.c, so that it gives environment 1 I/O privilege, but never gives that privilege to any other environment.

Make sure you can start the file environment without causing a General Protection fault. You should pass the "fs i/o" test in make grade. }
\par{在开始Exercise1之前，先简单介绍JOS文件系统的结构。}
\par{首先是几个概念：
  \begin{itemize}
  \item 扇区：磁盘读写的最小单位，在JOS中为512B。
  \item 块：文件系统分配的最小单位，必须是扇区大小的整数倍，在JOS中为4096B。
  \item 超级块：储存文件系统元信息的块，通常有许多拷贝，分散在文件系统的各个部分。
  \item 块位图：JOS中使用位图记录空闲块，1代表空闲，0代表占用。一块大小为4096B，即可以记录下4096*8=32768个文件块。
  \end{itemize}
下面是JOS中文件块的分布，0号块为bootloader，1号块为超级块，接下来连续的几块为块位图，其余都为真正的文件。
}
\par{JOS中使用File这个结构体来描述文件，包含文件号，文件对应的块和文件类型等等。当遇到目录文件时，将会读取文件信息以获得目录下的文件。当遇到普通文件时则不读取内容。}
\par{下面开始Exercise1，需要设置文件系统的环境，也就是envs[1]。让其具有I/O特权。也就是在env\_alloc的函数中加入一条判断语句，如果环境为envs[1]，那么就将eflags中的IOPL设置为3，否则设置为0。}
\section{Exercise 2}
\clbox{Implement the bc\_pgfault and flush\_block functions in fs/bc.c. bc\_pgfault is a page fault handler, just like the one your wrote in the previous lab for copy-on-write fork, except that its job is to load pages in from the disk in response to a page fault. When writing this, keep in mind that (1) addr may not be aligned to a block boundary and (2) ide\_read operates in sectors, not blocks.

The flush\_block function should write a block out to disk if necessary. flush\_block shouldn't do anything if the block isn't even in the block cache (that is, the page isn't mapped) or if it's not dirty. We will use the VM hardware to keep track of whether a disk block has been modified since it was last read from or written to disk. To see whether a block needs writing, we can just look to see if the PTE\_D "dirty" bit is set in the vpt entry. (The PTE\_D bit is set by the processor in response to a write to that page; see 5.2.4.3 in chapter 5 of the 386 reference manual.) After writing the block to disk, flush\_block should clear the PTE\_D bit using sys\_page\_map.

Use make grade to test your code. Your code should pass check\_bc, check\_super, and checkbitmap for a score of 20/100. }
\par{在JOS中限制了文件系统最大为3GB，从0x10000000到0xD0000000，这一段为block cache，分别对应每一个块。显然，不可能将整个文件系统读入内存，所以JOS实现了按需分配的机制，只有需要读或者写某个未映射在内存中的块时才将其映射到内存中。}
\par{bc\_pgfault这个函数就是默认的page fault handler，这个函数将发生错误的地址对应的磁盘块读入内存中。注意两点：1，地址可能不是页对齐的，需要将其ROUNDDOWN。2，ide\_read这个函数读的是扇区数，一个块所含的扇区数为BLKSECTS，所以调用ide\_read时要注意将数量设置为BLKSECTS。}
\begin{lstlisting}
  r = sys_page_alloc(0, diskaddr(blockno), PTE_P|PTE_W|PTE_U);
  if(r < 0)
    panic("sys_page_alloc:%e\n",r);
  r = ide_read(BLKSECTS * blockno, (void *)ROUNDDOWN(addr,PGSIZE), BLKSECTS);
  if(r < 0)
    panic("ide_read:%e\n",r);
\end{lstlisting}
\par{flush\_block函数将在内存中“脏”的块写入磁盘中。这个函数要做的工作就是：检查是否合法，调用ide\_write函数写入磁盘，去掉原来在页表项中的PTE\_D位。与之前的bc\_pgfault一样，addr可能不是页对齐的。}
\begin{lstlisting}
  if(!(va_is_mapped(addr) && va_is_dirty(addr)))
  {
    return;
  }
  addr = (void *)ROUNDDOWN(addr, PGSIZE);
  ide_write(blockno * BLKSECTS, addr, BLKSECTS);
  int r = sys_page_map(0, addr,0, addr, PTE_USER);
  if(r < 0)
    panic("sys_page_map:%e\n",r);
\end{lstlisting}
\section{Exercise 3}
\clbox{Use free\_block as a model to implement alloc\_block, which should find a free disk block in the bitmap, mark it used, and return the number of that block. When you allocate a block, you should immediately flush the changed bitmap block to disk with flush\_block, to help file system consistency.

Use make grade to test your code. Your code should now pass "alloc\_block" for a score of 25/100. }
\par{之前说过，JOS使用位图记录文件块的分发情况，free\_block中，直接将bitmap中对应记录该块的项置为1，代表这个块是空闲的。而alloc\_block中也类似，首先遍历所有的块，找到第一个空闲的块，将其置为使用，并将这个块写回磁盘。}
\begin{lstlisting}
  int i = 0;
  for(i = 0; i < super->s_nblocks; i++)
    if(block_is_free(i))
      break;
  if(i == super->s_nblocks)
    return -E_NO_DISK;
  bitmap[i/32] &= ~(1 << (i % 32));
  flush_block(diskaddr(2 + i/BLKBITSIZE));//bitmap starts at block 2
  return i;
\end{lstlisting}
\section{Exercise 4}
\clbox{Implement file\_block\_walk and file\_get\_block. file\_block\_walk maps from a block offset within a file to the pointer for that block in the struct File or the indirect block, very much like what pgdir\_walk did for page tables. file\_get\_block goes one step further and maps to the actual disk block, allocating a new one if necessary.

Use make grade to test your code. Your code should pass "file\_open", "file\_get\_block", and "file\_flush/file\_truncated/file rewrite" for a score of 40/100. }
\par{file\_block\_walk这个函数很像之前的pgdir\_walk，返回的是第filebno个块对应的槽的地址。这个函数可以分为两个部分考虑，如果位于直接块中则直接返回。如果在非直接块中，则根据alloc判断是否分配新的块，如果分配了新的块则需要清0，并将返回值设置为以新块为基址加上一个偏移量（filebno-10）。有一个需要注意的点，就是filebno是从0开始的！在计算偏移量的时候不要算错了。}
\begin{lstlisting}
  if(filebno >= NDIRECT + NINDIRECT)
    return -E_INVAL;
  if(filebno < NDIRECT)
  {
    if(ppdiskbno)
      *ppdiskbno = &f->f_direct[filebno];
    return 0;
  }  
  if(f->f_indirect == 0)
  {
    
    if(alloc == 0)
      return -E_NOT_FOUND;
    //allocate a block
    int block = alloc_block();
    if(block < 0)
      return block;
    memset(diskaddr(block), 0, BLKSIZE);
    f->f_indirect = block;
  }
  *ppdiskbno = &((uint32_t *)diskaddr(f->f_indirect))[filebno - NDIRECT];
  return 0;
\end{lstlisting}
\par{file\_get\_block这个函数将blk设置为指向这个文件第filebno个块的首地址。有了之前的file\_block\_walk函数，这个函数的实现就简单了许多。首先得到指向对应块的地址，如果为0则分配一块。然后根据是否位于直接块做进一步工作，如果处于直接块则将f\_direct对应项设置好。如果在间接块中，则使用diskaddr函数能够将间接块的号码转为虚拟地址（在这里间接块不可能为0，因为alloc\_block已经为其分配了一块），以这个地址为基址计算偏移量，将得到新块的号放入即可。最后设置blk指向新块代表的虚拟地址。}
\begin{lstlisting}
  if(filebno >= NDIRECT + NINDIRECT)
    return -E_INVAL;
  uint32_t * entry;
  int r = file_block_walk(f, filebno, &entry, 1);
  if(r < 0)
    return r;
  if(*entry == 0)
  {//alloc a block
    r = alloc_block();
    if(r < 0)
      return r;
    if(filebno < NDIRECT)
      f->f_direct[filebno] = r;
    else
    {
      ((uint32_t *)diskaddr(f->f_indirect))[filebno - NDIRECT] = r;
    }
    *blk = diskaddr(r);
  }
  else
    *blk = (char *)diskaddr(*entry);
  return 0;
\end{lstlisting}
\section{Exercise 5}
\clbox{Implement serve\_read in fs/serv.c and devfile\_read in lib/file.c.

serve\_read's heavy lifting will be done by the already-implemented file\_read in fs/fs.c (which, in turn, is just a bunch of calls to file\_get\_block). serve\_read just has to provide the RPC interface for file reading. Look at the comments and code in serve\_set\_size to get a general idea of how the server functions should be structured.

Likewise, devfile\_read should pack its arguments into fsipcbuf for serve\_read, call fsipc, and handle the result.

Use make grade to test your code. Your code should pass "lib/file.c" and "file\_read" for a score of 50/100. }
\par{接下来的工作就是实现其他环境和文件系统的通信了，流程图如下：}
\newpage
\begin{verbatim}
      Regular env           FS env
   +---------------+   +---------------+
   |      read     |   |   file_read   |
   |   (lib/fd.c)  |   |   (fs/fs.c)   |
...|.......|.......|...|.......^.......|...............
   |       v       |   |       |       | RPC mechanism
   |  devfile_read |   |  serve_read   |
   |  (lib/file.c) |   |  (fs/serv.c)  |
   |       |       |   |       ^       |
   |       v       |   |       |       |
   |     fsipc     |   |     serve     |
   |  (lib/file.c) |   |  (fs/serv.c)  |
   |       |       |   |       ^       |
   |       v       |   |       |       |
   |   ipc_send    |   |   ipc_recv    |
   |       |       |   |       ^       |
   +-------|-------+   +-------|-------+
           |                   |
           +-------------------+
\end{verbatim}
\par{可以看到，在用户态发送一个请求给文件系统最终可以产生对文件的某个操作，现在首先实现的就是读文件的操作。}
\par{首先来看serve\_read，参照serve\_set\_size函数的实现方法，首先得到一个Openfile的对象o，o中包含了文件的seek指针，本身的文件对象，以及对应的Fd页（类似文件描述符）。接着使用这个对象中的信息调用文件系统中的API完成函数。}
\par{在serve\_read中，需要使用的API是file\_read，其中seek position可以在fd文件中的fd\_offset中找到，需要注意的是，由于ret\_buf只有PGSIZE这么大，所以当欲读的数据量过大的时候需要将其转换成PGSIZE。还有一点，由于发送的结构是一个union，所以当ret\_buf被填充时原来的size和fileid都被覆盖了，如果需要使用则要用临时变量保存起来。}
\par{总的来说，这个函数的流程就是：找到对应openfile，调用fileread，设置seek position，返回读入的字节。}
\begin{lstlisting}
  int r;
  struct OpenFile * o;
  if ((r = openfile_lookup(envid, req->req_fileid, &o)) < 0)
    return r;
  int fileid = req->req_fileid;
  size_t count = req->req_n;
  r = file_read(o->o_file, ret->ret_buf, MIN(count,PGSIZE), o->o_fd->fd_offset);
  if(r < 0)
    return r;
  o->o_fd->fd_offset += MIN(r, PGSIZE);
  return MIN(r, PGSIZE);
\end{lstlisting}
\par{下面是devfile\_read，这个函数设置fsipcbuf的对应项（read.req\_fileid,read.req\_n），接着发送FSREQ\_READ这个消息，由于在serv.c中我们将文件的信息重新写入了fsipcbuf中，所以需要将这里的数据移入到buf中，最后return的是读入的字节。}
\begin{lstlisting}
  fsipcbuf.read.req_fileid = fd->fd_file.id;
  fsipcbuf.read.req_n = n;
  int r = fsipc(FSREQ_READ, NULL);
  if(r < 0)
    return r;
  buf = memmove(buf, fsipcbuf.readRet.ret_buf, r);
  return r;
\end{lstlisting}
\section{Exercise 6}
\clbox{Implement serve\_write in fs/serv.c and devfile\_write in lib/file.c.

Use make grade to test your code. Your code should pass "file\_write" and "file\_read after file\_write" for a score of 60/100. }
\par{接下来的两个函数与之前的serve\_read和devfile\_read几乎类似。devfile\_write与devfile\_read比较大的区别就是先将内存中的数据移到fsipcbuf中，再发送FSREQ\_WRITE。而serve\_write与serve\_read几乎没有区别，仅仅是将file\_read替换成file\_write。}
\section{Exercise 7}
\clbox{Implement open. The open function must find an unused file descriptor using the fd\_alloc() function we have provided, make an IPC request to the file system environment to open the file, and return the number of the allocated file descriptor. Be sure your code fails gracefully if the maximum number of files are already open, or if any of the IPC requests to the file system environment fail.

Use make grade to test your code. Your code should pass "open", "motd display", and "motd change" for a score of 85/100. }
\par{结构Fd储存的是文件的描述信息，系统提供了最多MAXFD（32）个文件描述符供一个环境打开。在open函数中，首先获得一个文件描述符，然后将fsipcbuf的omode设置为mode，设置path，发送FSREQ\_OPEN消息。如果open失败了，要记得使用fd\_close释放文件描述符，最后使用fd2num返回文件描述符的号码。}
\begin{lstlisting}
  if(sizeof(path) >= MAXPATHLEN)
    return -E_BAD_PATH;
  int r;
  struct Fd * fd;
  r = fd_alloc(&fd);
  if(r < 0)
    return r;
  fsipcbuf.open.req_omode = mode;
  memmove(fsipcbuf.open.req_path, path, MAXPATHLEN);
  r = fsipc(FSREQ_OPEN, fd);
  if(r < 0)
  {
    fd_close(fd, 1);
    return r;
  }
  return fd2num(fd);
\end{lstlisting}
\section{Exercise 8}
\clbox{spawn relies on the new syscall sys\_env\_set\_trapframe to initialize the state of the newly created environment. Implement sys\_env\_set\_trapframe. Test your code by running the user/icode program from kern/init.c, which will attempt to spawn /init from the file system. (Hint: If this fails in diskaddr, something's probably wrong with your indirect block code, since this is the first time we've used files that large.)

Use make grade to test your code. Your code should score 100/100. }
\par{这个函数十分简单，首先得到对应环境，对tf进行检查，最后将环境的tf设置为tf，并将FL\_IF置位。}
\begin{lstlisting}
  if(sizeof(path) >= MAXPATHLEN)
    return -E_BAD_PATH;
  int r;
  struct Fd * fd;
  r = fd_alloc(&fd);
  if(r < 0)
    return r;
  fsipcbuf.open.req_omode = mode;
  memmove(fsipcbuf.open.req_path, path, MAXPATHLEN);
  r = fsipc(FSREQ_OPEN, fd);
  if(r < 0)
  {
    fd_close(fd, 1);
    return r;
  }
  return fd2num(fd);
  
\end{lstlisting}
\end{document}




